1. Field of the Invention
The present invention generally relates to devices for aiding an analysis of infeasible solutions and unbounded solutions and, particularly, relates to a device for aiding an analysis of infeasible solutions and unbounded solutions. The device is used for finding a cause of the infeasible solutions and unbounded solutions in mathematical programming.
More particularly, the present invention relates to a device using a GUI (graphical user interface) for aiding in an analysis of infeasible solutions and unbounded solutions which are obtained through an optimization of a mathematical programming system, when the mathematical programming is applied to the designing of a production plan and an operation plan for petroleum plants, chemical plants, and the like.
2. Description of the Related Art
In order to find a cause of infeasible solutions and unbounded solutions, GUI is used to provide a user interface between an operator and a computer, through which graphical components such as pull-down menus, windows, icons, etc., are manipulated by using a pointing device. In general, the cause of infeasible solutions and unbounded solutions is found by using information displayed through GUI by following the procedure detailed below:
Step 1) identifying variables causing the infeasible solutions and the unbounded solutions;
Step 2) checking whether appropriate data is set for these variables;
Step 3) correcting the data if it is not appropriate.
In general, a modeling system which is used for generating model data of mathematical programing has an advantage in that a generation of process flows and data entry can be conducted without taking into account a formulation of the mathematical programming. In such a modeling system, the model data is generated automatically without an attention being paid to each variable name. Thus, when infeasible solutions and unbounded solutions are obtained, it takes time to determine which part of the process flow corresponds to the variables of the cause of the infeasible and unbounded solutions.
Accordingly, it is expected that information regarding which part of the process flow corresponds to which variable name of the model data will be provided to the user, when the modeling system is used.
In the following, a process of obtaining an optimal solution used in various programming methods will be described.
FIG. 1 is a block diagram of a system for aiding an analysis. The system shown in the figure includes a modeling system 100, a variable-map file 200, a model-data file 300, a solution-information file 400, a mathematical-programming system 500, a display device 600, and a model-generation-information file 900.
In general, the modeling system 100 can express an accurate mathematical-programming model by using given data, and is capable of incorporating new data which are not used in initial modeling. In an example of FIG. 1, the modeling system 100 generates the variable-map file 200, the model-data file 300, and the model-generation-information file 900. The modeling system 100 shows operation results calculated by the mathematical-programming system 500 to the user through the display device 600.
The variable-map file 200 contains variable names of the model data generated by the modeling system 100, and contains path names representing which parts of the process flow correspond to which variable names.
FIG. 2 is a chart showing an example of the variable map. The variable map contains variable names automatically given by the modeling system 100 and the path names representing which parts of the process flow correspond to which variable names. In FIG. 2, the variable names starting with "R" refer to row-variable names, and variable names starting with "C" refer to column-variable names. In the columns section of FIG. 2, the row indicated by (*) means that a variable C0000007, named by the modeling system, represents input data of a first period on a line L1 of the process flow.
The model-data file 300 stores the model data generated by the modeling system 100.
The solution-information file 400 contains information on a solution which is obtained through optimization by the mathematical-programming system 500. The information on a solution is written in the solution-information file 400 not only when an optimum solution is obtained through the optimization but also when a infeasible solution or a unbounded solution is obtained.
The model-generation-information file 900 is a file in which detailed information on each variable is written when the modeling system 100 generates the model data.
FIG. 3 is a chart showing an example of the model-generation-information file. The part indicated by (*) in FIG. 3 means that an expression R0000014 represents an amount of consumption of the first period on a line L9 of the process flow, and that a difference between a variable C0000013 and a variable C0000033 is zero, i.e., an output amount from a device on the line L9 is the same in the first period as the output amount of the line L9 from the entire process flow. Also, an upper bound and a lower bound which are set for the variables C0000013 and C0000033 are written in the model-generation-information file 900.
A method by which the mathematical-programming system 500 determines if a solution is infeasible or unbounded will be described below. When the solution cannot satisfy all constraints, the solution is found infeasible. When the constraints are not enough to obtain a bounded solution such that an absolute value of an objective function can be as large as possible, the solution is unbounded.
A method of the determination when the simplex method is used as an optimization method will be described. The simplex method searches for a node at which the objective function becomes the largest or the smallest, while moving from a node to a node which is made up by the constraints. For example, the nodes are apexes of a n-dimensional polyhedron when n constraints are imposed. Here, the movement from node to node is accomplished by using mathematical matrix operations.
An infeasible solution in the simplex method is a solution at a node where a sum of the amounts which do not satisfy the constraints increases or does not change for a search in any direction. That is, the infeasible solution is a solution when this sum does not decrease. An unbounded solution is a solution at a node where an absolute value of the objective function can become infinitely large while satisfying the constraints. For example, when the objective function is to be maximized, the unbounded solution is a solution when a variable which has a positive coefficient and can become infinitely large is found.
The display device 600 displays various information which is used for obtaining records and end results of an optimization process carried out by the mathematical-programming system 500. For example, types of displays for showing the information include an output-information-display window, a solution accessing window, and an infeasible/unbounded-solution-display window.
FIG. 4 is an illustrative drawing for showing an example of the display of the related art. In the figure, a process-flow window 610, a output-information-display window 620, a solution accessing window 630, and a value setting table 650 are shown. The process-flow window 610 is used by the user for determining the process flow and configuration of devices (processing elements). The output-information-display window 620 is used for displaying the record of the optimization process. The solution accessing window 630 is used for displaying the end result of the optimization process. These windows are displayed when the user selects them by using a pointing device.
In the process-flow window 610, the user by using the pointing device enters lines (L1 through L12 in the example of FIG. 4) representing flows of various elements and boxes (B1 through B4) representing devices for processing these elements.
FIG. 5 is an illustrative drawing showing the process-flow window 610 in more detail. At the bottom of the process-flow window 610, a result-display field 611 is provided. The result-display field 611 is used for displaying a value of the objective function and a condition of the solution as to whether it is an optimal solution, an infeasible solution, or a unbounded solution, obtained through the optimization process.
The output-information-display window 620 displays a record on the model-data generation which is conducted by the modeling system 100 for the mathematical programming, a record on an operation of the mathematical-programming system 500, and a record on a process of the modeling system 100 obtaining the solution information of the mathematical-programming system 500.
The solution accessing window 630 displays the solution obtained by the mathematical-programming system 500 by reading it from the solution-information file 400.
The value setting table 650 is used for setting the upper bound and the lower bound for input/output values of each device (e.g., B1 through B4) and the entire process flow, and for setting various conditions and the like which are necessary for the optimization process. The setting is conducted for each of the devices or for the entire process flow. Also, in the value setting table 650, solutions obtained by the mathematical-programming system 500 can be displayed for each data entry.
FIG. 6 is a chart showing an example of the value setting table. The example of FIG. 6 shows value setting tables for setting input/output data for the device B1. An upper table is an input-data table for the device B1, and the lower table is an output-data table for the device B1. Columns of the upper bound and the lower bound are used by the user for entering values, and an activity column is used for displaying solutions obtained through the optimization process by the mathematical-programming system 500.
FIG. 7 is a flowchart of a process of an analysis aiding system of the related art, and is used for explaining an operation of the system of FIG. 1.
At a step S101, a process flow is created by the user on the display device 600 using the modeling system 100.
At a step S102, conditions are entered by the user in the value setting table 650 using the modeling system 100. Here, examples of these conditions, which are required by the mathematical-programming system 500, include a condition on an amount of procured supplies as to the number of tons of supplies necessary, a condition on the yield as to what percentage of the yield must be maintained on average in factory production, etc. These conditions can be set for each of the devices or the entire process flow.
At a step S103, the modeling system 100 generates the model data, and provides variable names in an order. Also, the modeling system 100 stores in the variable-map file 200 these variable names along with the path names indicating which parts of the process flow correspond to these variable names.
At a step S104, the modeling system 100 stores in the model-generation-information file 900 the detailed information on the expressions and the variables regarding the generating process of the model data.
At a step S105, the modeling system 100 stores the model data in the model-data file 300.
At a step S106, the mathematical-programming system 500 reads the model data from the model-data file 300, carries out the optimization process, and stores the solutions in the solution-information file 400.
At a step S107, the modeling system 100 accesses the solution-information file 400 to obtain the solution condition by reading the result of the optimization process of the mathematical-programming system 500.
At a step S108, the modeling system 100 displays the result of the optimization process in the process-flow window 610 on the display device 600.
At a step S109, the modeling system 100 displays the result of the optimization process in the value setting table 650 on the display device 600.
At a step S110, a check is made whether the solution is one of the infeasible solution and the unbounded solution. When the solution is one of the infeasible solution and the unbounded solution, this determination is displayed as the solution condition in the result-display field 611 of the process-flow window 610. or the determination can be shown in the record on the operation of the mathematical-programming system 500, which record is displayed in the output-information-display window 620. When the solution is one of the infeasible solution and the unbounded solution, the procedure goes to a step S111. Otherwise, the procedure ends at this point.
At a step S111, the user looks up in the output-information-display window 620 the variable names of the variables causing the infeasible solution or the unbounded solution.
FIGS. 8A through 8C are illustrative drawings showing examples of the output-information-display window 620. FIG. 8A shows an example in which an optimal solution is obtained with a value of the objective function being "210.00000".
FIG. 8B shows an example in which an infeasible solution is caused by variables R0000012, R0000018, and R0000032. In FIG. 8B, a column b indicates row-variable numbers of the variables of the cause, a column c indicates row-variable names of the variables of the cause, a column d indicates variable numbers in the base at rows causing the infeasible solution, and a column e indicates variable names in the base at rows causing the infeasible solution.
FIG. 8C show an example in which an unbounded solution is caused by a variable C0000005. In FIG. 8C, a column f indicates variable numbers of the variables causing the unbounded solution, and a column g indicates variable names of the variables of the cause.
At a step S112, the user looks up the variable-map file 200, the model-generation-information file 900, or the solution accessing window 630 to determine, based on the path names, which parts of the process flow correspond to the variables of the cause. For example, when a variable R0000009 shown in the output-information-display window 620 is the cause of the infeasible solution, the user looks up the variable-map file 200 to pick up a path name ".INPUT(L1)" corresponding to the variable R0000009. By doing so, the user can know that an input amount on the line L1 of the process flow is the cause of the infeasible solution.
When the model-generation-information file 900 as shown in FIG. 3 is looked up, for example, the detailed information regarding the generation of the expression R0000014 is searched for and obtained. By doing so, the user can know that the expression R0000014 is comprised of the variables C0000013 and C0000033 and that these variables are the causes of the infeasible solution.
When the solution accessing window 630 as shown in FIG. 9 is looked up and the variable C0000007 is known to be a cause of an unbounded solution, for example, a path name ".INPUT(L1).T1" of the variable C0000007 is searched for and obtained in the solution accessing window 630. By doing so, the user can know that an input amount in the first period on the line L1 of the process flow is the cause of the unbounded solution.
In this manner, the user extracts elements causing an infeasible solution and an unbounded solution, and analyzes these elements.
However, in the former technique, the user is required to determine, based on the path names, which elements of the process flow correspond to the variables causing an infeasible solution or an unbounded solution. The user has to do this by looking up the variable-map file or the solution accessing window based on the variable names of the causes, wherein the variable names are obtained from the information generated by the mathematical-programming system. Thus, although the modeling system is expected to allow users to design the mathematical programming without having to pay attention to its formulation, the user has to start the analysis from the model data automatically generated by the modeling system.
Thus, the user has to follow the procedure as described above in order to find the cause of the infeasible solution or the unbounded solution, so that the work load on the user is excessively large.
Accordingly, there is a need for an analysis aiding device which can provide a user with information easy to understand and useful for analyzing an infeasible solution or an unbounded solution obtained through the optimization process.
Also, there is a need for an analysis adding device which can enhance elements on the process flow causing an infeasible solution or an unbounded solution by showing them in a distinctive color or in a blinking appearance.
Furthermore, there is a need for an analysis aiding device which can enhance elements causing an infeasible solution or an unbounded solution by showing them in a distinctive color or in a blinking appearance when a process flow has a hierarchical structure.
Also, there is a need for an analysis aiding device which can display variable names and path names of variables causing an infeasible solution or an unbounded solution in the solution accessing window, and can attach descriptions of path names.
Furthermore, there is a need for an analysis aiding device which can display variable names and path names of variables causing an infeasible solution or an unbounded solution in a solution-information-display window, and can attach descriptions of path names.
Also, there is a need for an analysis aiding device which allow a user to easily find the cause of an infeasible solution and an unbounded solution by simultaneously displaying the process flow and the value setting table.